package 算法.leetcode.labuladong.二叉树;

import 算法.leetcode.offer.base.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author lchenglong
 * @date 2022/6/24
 */
public class 把二叉搜索树转化为累加树 {
    static class Solution {

        public static void main(String[] args) {
            Solution solution = new Solution();
            TreeNode root = TreeNode.init(new ArrayList<>(Arrays.asList(4,1,6,0,2,5,7,null,null,null,3,null,null,null,8)));
            root = solution.convertBST(root);
            TreeNode.print(root);
        }
        public TreeNode convertBST(TreeNode root) {
            travel(root);
            return root;
        }
        int sum = 0;
        public void travel(TreeNode root){
            // base case
            if (root == null) return ;
            travel(root.right);
            sum+= root.val;
            root.val = sum;
            travel(root.left);
        }
    }
}
